/**
 * 
 */
package sg.edu.nus;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * @author Christian
 *
 */
public class FastMiner implements RoleMiner {

	private Map<Integer, Integer[]> initRoles;
	private Map<Integer, Integer> initRolesCount;
	private Map<Integer, Integer[]> genRoles;
	private Map<Integer, Integer> genRolesCount;
	private TreeMap<Integer, List<Integer>> countSortedResult;
	
	public FastMiner(List<Integer[]> usersWithPermissions, int initRolePriority) {
		initRoles = new HashMap<Integer, Integer[]>();
		initRolesCount = new HashMap<Integer, Integer>();
		genRoles = new HashMap<Integer, Integer[]>();
		genRolesCount = new HashMap<Integer, Integer>();
		// mine roles
		mineRoles(usersWithPermissions);
		// create sorted result
		countSortedResult = getSortedResult(initRolePriority);
	}

	private void mineRoles(List<Integer[]> usersWithPermissions) {
		// find initial roles
		int hashCode = 0;
		for(Integer[] userPermissions : usersWithPermissions) {
			// ignore empty set
			if(userPermissions.length == 0) continue;
			
			hashCode = Arrays.hashCode(userPermissions);
			// check if role already exists
			if(initRoles.containsKey(hashCode)) {
				// increment count
				initRolesCount.put(hashCode, (initRolesCount.get(hashCode)) + 1);
			}
			else {
				// add initial role with count
				initRoles.put(hashCode, userPermissions);
				initRolesCount.put(hashCode, 1);
			}
		}
		
		// find new roles
		List<Integer> initRoleKeyList = new ArrayList(initRoles.keySet());
		int listSize = initRoleKeyList.size();
		Integer[] roleI, roleJ, newRole;
		int keyI, keyJ, newRoleKey;
		int countI = 0, countJ = 0;
		Map<Integer, Set<Integer>> contributingRolesMap = new HashMap<Integer, Set<Integer>>();
		Set<Integer> contributingRoles = null;
		
		for(int i = 0; i < listSize; i++) {
			// get role and count i
			keyI = initRoleKeyList.get(i);
			roleI = initRoles.get(keyI);
			countI = initRolesCount.get(keyI);
			// intersect init roles
			for(int j = i; j < listSize; j++) {
				// get role and count i
				keyJ = initRoleKeyList.get(j);
				roleJ = initRoles.get(keyJ);
				countJ = initRolesCount.get(keyJ);
				// calculate intersection if i and j
				newRole = intersectSortedArrays(roleI, roleJ);
				// check if empty set
				if(newRole.length == 0) continue;
				newRoleKey = Arrays.hashCode(newRole);
				// check if new role not in gen roles
				if(!genRoles.containsKey(newRoleKey)) {
					// add new role
					genRoles.put(newRoleKey, newRole);
					genRolesCount.put(newRoleKey, (countI + countJ));
					// add contributing role keys for new role
					contributingRoles = new HashSet<Integer>();
					contributingRoles.add(keyI);
					contributingRoles.add(keyJ);
					contributingRolesMap.put(newRoleKey, contributingRoles);
				}
				// new role already in gen roles
				else {
					// get contributing roles
					contributingRoles = contributingRolesMap.get(newRoleKey);
					// check if i has not contributed before to new role
					if(!contributingRoles.contains(keyI)) {
						// increment count with count i
						genRolesCount.put(newRoleKey, genRolesCount.get(newRoleKey) + countI);
						// add i as contributing role
						contributingRoles.add(keyI);
					}
					// check if j has not contributed before to new role
					if(!contributingRoles.contains(keyJ)) {
						// increment count with count j
						genRolesCount.put(newRoleKey, genRolesCount.get(newRoleKey) + countJ);
						// add j as contributing role
						contributingRoles.add(keyJ);
					}
				}
			}
		}
	}

	/**
	 * Fast intersection algorithm which assumes that both arrays are sorted in ascending order.
	 */
	private Integer[] intersectSortedArrays(Integer[] arrA, Integer[] arrB) {
		int aIndex = 0;
		int bIndex = 0;
		int aLength = arrA.length;
		int bLength = arrB.length;
		// create result array long enough for full match
		List<Integer> list = new ArrayList<Integer>(Math.max(aLength, bLength));
		
		while (aIndex < aLength && bIndex < bLength) {
			// match found
			if(arrA[aIndex] == arrB[bIndex]) {
				list.add(arrA[aIndex]);
				aIndex++;
				bIndex++;
			}
			// check if current element in arr A is lower than in arr B
			else if (arrA[aIndex] < arrB[bIndex]) {
				aIndex++;
			}
			// current element in arr B is lower than in arr A
			else {
				bIndex++;
			}
		}
		
		if(list.size() == 0) return new Integer[0];
		Integer[] res = new Integer[list.size()];
		
		return list.toArray(res);
	}
	
	private TreeMap<Integer, List<Integer>> getSortedResult(int priority) {
		// sort found roles by count
		TreeMap<Integer, List<Integer>> sortedResult = new TreeMap<Integer, List<Integer>>();
		int roleCount = 0;
		List<Integer> roleList = null;
		for(Integer roleKey : genRoles.keySet()) {
			// get role count
			roleCount = genRolesCount.get(roleKey);
			// get original role count and prioritise
			if(initRoles.containsKey(roleKey)) {
				roleCount += initRolesCount.get(roleKey) * priority;
			}
			// check if count already exist
			roleList = sortedResult.get(roleCount);
			if(roleList == null) {
				roleList = new ArrayList<Integer>();
			}
			roleList.add(roleKey);
			// add to map
			sortedResult.put(roleCount, roleList);
		}
		
		return sortedResult;
	}
	
	public void dumpData() {
		int roleId = 0;
		System.out.println("\nFast miner roles with permissions:");
		System.out.println("==================================");
		System.out.println("Init Roles:");
		System.out.println("-----------");
		for(Integer roleKey : initRoles.keySet()) {
			System.out.println("Init Role=" + roleId + ", permissions: " + Arrays.toString(initRoles.get(roleKey)) + 
					", count=" + initRolesCount.get(roleKey));
			roleId++;
		}
		
		System.out.println("\nGen Roles:");
		System.out.println("-----------");
		for(Integer roleKey : genRoles.keySet()) {
			System.out.println("Role=" + roleId + ", permissions: " + Arrays.toString(genRoles.get(roleKey)) + 
					", count=" + genRolesCount.get(roleKey));
			roleId++;
		}
		System.out.println("");
		
		// print sorted result
		for(int count : countSortedResult.descendingKeySet()) {
			System.out.print("count=" + count + ", roles: ");
			for(Integer roleKey : countSortedResult.get(count)) {
				System.out.print(Arrays.toString(genRoles.get(roleKey)) + ", ");
			}
			System.out.println("");
		}
	}

	public Map<Integer, Integer[]> getInitRoles() {
		return initRoles;
	}

	public Map<Integer, Integer> getInitRolesCount() {
		return initRolesCount;
	}

	public Map<Integer, Integer[]> getGenRoles() {
		return genRoles;
	}

	public Map<Integer, Integer> getGenRolesCount() {
		return genRolesCount;
	}

	public TreeMap<Integer, List<Integer>> getCountSortedResult() {
		return countSortedResult;
	}
	
}
